Data that is stored or transmitted may be protected against storage media failures or other loss by storing extra copies, by storing additional redundant information, or in other ways. One type of redundancy based protection involves using erasure coding. Erasure coding uses additional redundant data to produce erasure codes that protect against ‘erasures’ where data portions that are lost can be reconstructed from the surviving data. The application of erasure codes to data storage may typically have been for the purpose of recovering data in the face of failures of hardware elements storing the data. Redundant arrays of independent disks (RAID) storage systems have protected data using systematic erasure codes.
Adding redundancy introduces overhead that consumes more storage capacity or transmission bandwidth, which in turn adds cost. The overhead added by erasure code processing tends to increase as the protection level provided increases. To enhance data protection, different approaches for storing redundant copies of items have been employed. Erasure codes are one such approach. An erasure code is a forward error correction (FEC) code for the binary erasure channel. The FEC facilitates transforming a message of k symbols into a longer message with n symbols so that the original message can be recovered from a subset of the n symbols, k and n being integers, n>k. The symbols may be individual items (e.g., characters, bytes) or groups of items. The original message may be, for example, a file. The fraction r=k/n is called the code rate, and the fraction k′/k, where k′ denotes the number of symbols required for recovery, is called the reception efficiency. Optimal erasure codes have the property that any k out of the n code word symbols are sufficient to recover the original message. Optimal codes may require extensive memory usage, CPU time, or other resources when n is large. Erasure coding approaches may seek to create the greatest level of protection with the least amount of overhead via optimal or near optimal coding. Different types of erasure codes have different efficiencies and tradeoffs in terms of complexity, resources, and performance.
Erasure codes are described in coding theory. Coding theory is the study of the properties of codes and their fitness for a certain purpose (e.g., backing up files). Codes may be used for applications including, for example, data compression, cryptography, error-correction, and network coding. Coding theory involves data compression, which may also be referred to as source coding, and error correction, which may also be referred to as channel coding. Fountain codes are one type of erasure code.
Fountain codes have the property that a potentially limitless sequence of encoding symbols may be generated from a given set of source symbols in a manner that supports ideally recovering the original source symbols from any subset of the encoding symbols having a size equal to or larger than the number of source symbols. A fountain code may be optimal if the original k source symbols can be recovered from any k encoding symbols, k being an integer. Fountain codes may have efficient encoding and decoding algorithms that support recovering the original k source symbols from any k′ of the encoding symbols with high probability, where k′ is just slightly larger than k. A rateless erasure code is distinguished from an erasure code that exhibits a fixed code rate.
Storage systems may employ rateless erasure code technology (e.g., fountain codes) to provide a flexible level of data redundancy. The appropriate or even optimal level of data redundancy produced using a rateless erasure code system may depend, for example, on the number and type of devices available to the storage system. The actual level of redundancy achieved using a rateless erasure code system may depend, for example, on the difference between the number of readable redundancy blocks (e.g., erasure codes) written by the system and the number of redundancy blocks needed to reconstruct the original data. For example, if twenty redundancy blocks are written and only eleven redundancy blocks are needed to reconstruct the original data that was protected by generating and writing the redundancy blocks, then the original data may be reconstructed even if nine of the redundancy blocks are damaged or otherwise unavailable. This may be referred to as an “11 of 20” erasure code system.
An erasure code (EC) system may be described using an A/B notation, where B describes the total number of encoded symbols that can be produced for an input message and A describes the minimum number of the B encoded symbols that are required to recreate the message for which the encoded symbols were produced. By way of illustration, in a 10 of 16 configuration, or EC 10/16, sixteen encoded symbols could be produced. The 16 encoded symbols could be spread across a number of drives, nodes, or geographic locations. The 16 encoded symbols could even be spread across 16 different locations. In the EC 10/16 example, the original message could be reconstructed from 10 verified fragments. Conventionally, the 16 encoded symbols have been treated equally.
Prior Art FIG. 1 illustrates an example set of systematic erasure codes. Prior Art FIG. 1 illustrates an original message 100 that has sixteen symbols S1, S2, . . . S16 (k=16) and that reads “original message”. While the symbol size is one character, different symbol sizes may be employed. Message 100 is provided to erasure encoder 110. Erasure encoder 110 uses a generator matrix 120 to produce erasure codes 130. In this example, erasure encoder 110 produces erasure codes EC1, EC2, . . . ECn (n>k). The erasure codes include systematic erasure codes EC1 . . . EC16 (EC1 . . . ECk), which correspond directly to S1 . . . S16 (S1 . . . Sk). In this embodiment, at least EC1 . . . EC16 may be the same size as S1 . . . S16. For example, if the symbols S1 . . . S16 are one byte each, then the symbols EC1 . . . EC16 may also be one byte each. The erasure codes also include EC17 . . . ECn (ECk+1 . . . ECn), which do not correspond to any of S1 . . . Sk. In one embodiment, ECk+1 . . . ECn may be parity information. In another embodiment, ECk+1 . . . ECn may be other information that facilitates recreating the original message. In this embodiment, ECk+1 . . . ECn do not need to be the same size as S1 . . . S16. For example, if S1 . . . S16 are one byte, ECk+1 . . . ECn do not have to be one byte. While the systematic erasure codes are illustrated as being generated in order and in locations directly corresponding to the input message, in some embodiments, the systematic erasure codes may be distributed through the ECn codes and may be out of order.
The original message 100 can be recreated from any 16 of the systematic erasure codes EC1 . . . ECn. If EC1 . . . ECk are available, then original message 100 can be recreated without performing erasure code decoding. If any of EC1 . . . ECk are not available, then original message 100 can still be recreated but erasure code decoding would be necessary for at least one of ECk+1 . . . ECn.
Prior Art FIG. 2 illustrates an example set of non-systematic erasure codes. Prior Art FIG. 2 illustrates an original message 200 that also has sixteen symbols S1, S2, . . . S16 (k=16) and that reads “original message”. While the symbol size is one character, different (e.g., larger) symbol sizes are likely to be employed. Message 200 is provided to erasure encoder 210. Erasure encoder 210 uses a generator matrix 220 to produce erasure codes 230. In this example, erasure encoder 210 produces non-systematic erasure codes EC1, EC2, . . . ECn (n>k). EC1, EC2, . . . ECn do not correspond directly to any of S1 . . . S16 as was the case for systematic erasure codes 130 (Prior Art FIG. 1). Instead, EC1, EC2, . . . ECn are the result of processing symbols S1 . . . S16 with the matrix 220 as controlled by erasure encoder 210. EC1, EC2, . . . ECn do not have to be the same size as S1 . . . S16. For example, S1 . . . S16 may be one byte each that represent one ASCII character each while EC1, EC2, . . . ECn are two bytes each.
Prior Art FIG. 3 illustrates a generator matrix 300. Typically, an erasure coder uses a generator matrix like matrix 300 for encoding data. An input message (e.g., plaintext) and the generator matrix 300 may be processed to produce erasure codes. For example, an input message and generator matrix 300 may be multiplied together using matrix multiplication to produce erasure codes.
Prior Art FIG. 4 illustrates a generator matrix 400 for a systematic erasure code system where the upper sub-matrix is an identity matrix. When the systematic erasure code system uses generator matrix 400, some of the erasure codes produced may be symbols from the input message. Thus, for systematic erasure codes, the encoded symbols may be denoted [Sk:En] to reflect the fact that some encoded symbols are actually the original data (e.g., plaintext).
Prior Art FIG. 5 illustrates example erasure code generation using a generator matrix 500 and an input message 510. The input message 510 is multiplied by generator matrix 500 using matrix multiplication to produce erasure codes 520. While the input message 510 had k symbols, the erasure codes 520 may have n symbols, where n>=k. In general, at least k symbols are required to decode the data. Decoding processes may vary by erasure code approach. For a systematic erasure code approach, if the erasure codes corresponding to the original input symbols are available, then no “decoding” is required, only re-assembly is required.